/**
 * Created with IntelliJ IDEA.
 * Description:单链表
 * User: LXW
 * Date: 2021-12-02
 * Time: 14:09
 */
class Node {           //创建节点类
    public int val;     // 数值域
    public Node next;   // 指向下一个节点的引用


    public Node (int data) {
        this.val = data;
    }
}
public class MyLinklist {
    public Node head;     // 指向头结点的引用：头引用
    // 打印单链表
    public void display () {
        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    // 从指定位置打印单链表
    public void newdisplay (Node newhead) {
        Node cur = newhead;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    // 获取单链表的长度
    public int size () {
        Node cur = this.head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    // 头插法
    public void addFirst (int data) {
        Node node = new Node(data);
        node.next = head.next;
        head.next = node;
    }
    // 尾插法
    public void addLast (int data) {
        Node node = new Node(data);
        if (head == null) {            // 如果链表是空表需要进行特殊处理，否则后面的cur.next会出现空指针异常
            head = node;
            return;
        }
        Node cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;     // 如果前面是空表的情况没有处理的话，这里就会空指针异常
    }
    // 在任意位置插入一个节点
    public void addindex (int index,int data) {
        Node node = new Node(data);
        if (index < 0 || index > size()) {
            System.out.println("index位置不合法");
            return;
        }
        if (index == 0) {            // 在第一个位置插入直接调用头插法
            addFirst(data);
            return;
        }
        if (index == size()) {      // 在最后一个位置插入直接调用尾插法
            addLast(data);
            return;
        }
        Node cur = findIndex(index);    // 先找到index的前一个结点才能插入
        node.next = cur.next;
        cur.next = node;
    }
    // 找到index下标的前一个节点并返回节点地址
    public Node findIndex (int index) {
        Node cur = this.head;
        while (index-1 != 0) {
            cur = cur.next;
        }
        return cur;
    }
    // 删除第一次出现关键字key的节点
    public void removeKey (int key) {
        if (head == null) {
            System.out.println("此链表为空");
            return;
        }
        if (head.val == key) {
            head = head.next;
            return;
        }
        Node cur = findKey(key);
        if (cur == null) {
            System.out.println("没有你要删除的节点");
            return;
        }
        Node del = cur.next;
        cur.next = del.next;
    }
    // 找到第一次出现key节点的前一个节点的地址并返回
    public Node findKey (int key) {
        Node cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    // 删除所有值为key的节点
    public Node  removeAllKey (int key) {
        if (head == null) {
            System.out.println("此链表为空");
            return null;
        }
        Node cur = this.head;
        Node curNext = cur.next;
        while (curNext != null) {
            if (curNext.val == key) {
                cur.next = curNext.next;
                curNext = curNext.next;
            }else {
                cur = curNext;
                curNext = curNext.next;
            }
        }
        if (head.val == key) {         // 最后处理头节点
            head = head.next;
        }
        return head;
    }
}
